#include <stdio.h>

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
//hoare版本
int PartSort1(int* a, int left, int right)
{
	int key = left;
	while (left < right)
	{
		while (right > left && a[right] >= a[key])
			right -= 1;
		while (right > left && a[left] <= a[key])
			left += 1;
		swap(&a[left], &a[right]);
	}
	swap(&a[left], &a[key]);
	return left;
}


//假设按照升序对arr数组中的[left,right]区间中的元素进行排序
void quicksort(int* a, int left, int right)
{
	if (left >= right)
		return;
	//按照基准值对arr数组的[left，right]区间中的元素进行划分
	int mid = PartSort1(a, left, right);
	//划分成功后以mid为边界形成左右两部分[left,mid-1][mid+1,right]
	//递归排[left，mid-1]
	quicksort(a, left, mid - 1);
	//递归排[mid+1,right]
	quicksort(a, mid + 1, right);
}

int main()
{
    int a[] = { 9,8,7,6,5,4,3,2,1,0 };
	quicksort(a, 0, 9);
    for (int i = 0; i < 10; ++i) printf("%d ", a[i]);
        return 0;
}

